package com.hardy.leetcode;

import java.util.ArrayList;
import java.util.Arrays;

/**
 * 求一个集合的所有子集 User: Ruijie Date: 2016/9/20
 */
public class Subsets {

    public static ArrayList<ArrayList<Integer>> subsets1(int[] S) {
        if (S == null || S.length == 0) {
            return null;
        }
        Arrays.sort(S);
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        dfs(S, res, new ArrayList<Integer>(), 0);
        return res;
    }

    private static void dfs(int[] S, ArrayList<ArrayList<Integer>> res,
                            ArrayList<Integer> array, int start) {
        if(array.size()==2){
            res.add(new ArrayList<>(array));
        }
        for (int i = start; i < S.length; i++) {
            array.add(S[i]);
            dfs(S, res, array, i + 1);
            array.remove(array.size() - 1);
        }
    }

    public static ArrayList<ArrayList<Integer>> subsets(int[] S) {
        if (S == null || S.length == 0) {
            return null;
        }
        Arrays.sort(S);
        ArrayList<ArrayList<Integer>> res = new ArrayList<ArrayList<Integer>>();
        int len = S.length;
        int n = 1 << len;
        for (int i = 0; i < n; i++) {
            int j = i;
            int index = 0;
            ArrayList<Integer> subArr = new ArrayList<Integer>();
            while (j > 0) {
                if ((j & 1) == 1) {
                    subArr.add(S[index]);
                }
                index++;
                j = j >> 1;
            }
            res.add(subArr);
        }
        return res;
    }

    public static void main(String[] args) {
        int[] arr = {1,2,3,4};
        System.out.println(subsets1(arr));
    }
}
